외젠 샤를 카탈랑(Eugène Charles Catalan)이 1865년에 발견한
수열 로, 보통
C n C_n C n 으로 표기한다.
OEIS 에
A000108 수열로 등록되어 있다.
제9항까지의 값은 다음과 같다.
n n n 번째 카탈랑 수(Catalan Number)
C n C_n C n 는 다음
점화식 의 형태로 나타낼 수 있다.
C n + 1 = ∑ i = 0 n C i C n − i ( n ≥ 0 ) \displaystyle C_{n+1}=\sum_{i=0}^n C_i C_{n-i}~(n \ge 0) C n + 1 = i = 0 ∑ n C i C n − i ( n ≥ 0 ) ,
C 0 = 1 C_0=1 C 0 = 1
위 점화식은 생각보다 독특한 방법으로 풀리는데, 먼저 카탈랑 수의
생성함수 를 다음과 같이 정의하고
{ c ( x ) } 2 \left\{ c \left( x \right) \right\}^2 { c ( x ) } 2 을 계산해보면
c ( x ) = ∑ n = 0 ∞ C n x n = C 0 + C 1 x + C 2 x 2 + ⋯ ⋯ { c ( x ) } 2 = C 0 2 + ( C 0 C 1 + C 1 C 0 ) x + ( C 0 C 2 + C 1 2 + C 2 C 0 ) x 2 + ⋯ ⋯ + ( ∑ i = 0 n C i C n − i ) x n + ⋯ ⋯ \displaystyle c \left( x \right) = \sum_{n=0}^\infty C_n x^n = C_0 + C_1 x + C_2 x^2 + \cdots\cdots \\ \left\{ c \left( x \right) \right\}^2 = {C_0}^2 + \left( C_0 C_1 + C_1 C_0 \right)x + \left( C_0 C_2 + {C_1}^2 + C_2 C_0 \right) x^2 + \cdots\cdots + \left( \sum_{i=0}^n C_i C_{n-i} \right) x^n + \cdots\cdots c ( x ) = n = 0 ∑ ∞ C n x n = C 0 + C 1 x + C 2 x 2 + ⋯⋯ { c ( x ) } 2 = C 0 2 + ( C 0 C 1 + C 1 C 0 ) x + ( C 0 C 2 + C 1 2 + C 2 C 0 ) x 2 + ⋯⋯ + ( i = 0 ∑ n C i C n − i ) x n + ⋯⋯
점화식에 따라 합의 기호로 나타내어지는
x n x^n x n 의 계수가 최초 생성함수 식에서
x n + 1 x^{n+1} x n + 1 의 계수이므로 생성함수에 대해 다음과 같은 관계식이 성립한다.
c ( x ) = 1 + x { c ( x ) } 2 c \left( x \right) = 1 + x\left\{ c\left( x \right) \right\}^2 c ( x ) = 1 + x { c ( x ) } 2
위 이차 방정식을 풀면
c ( x ) = 1 ± 1 − 4 x 2 x = 2 1 ∓ 1 − 4 x c \left( x \right) = \dfrac{1 \pm \sqrt{1 - 4x}}{2x} = \dfrac 2{1 \mp \sqrt{1 - 4x}} c ( x ) = 2 x 1 ± 1 − 4 x = 1 ∓ 1 − 4 x 2 (복부호 동순)
이 되는데 위 식에서
x → 0 x \to 0 x → 0 일 때의 값
C 0 = 1 C_0 = 1 C 0 = 1 이 존재하는 경우는
1 − 1 − 4 x 2 x \dfrac{1 - \sqrt{1 - 4x}}{2x} 2 x 1 − 1 − 4 x 뿐이며, 이 식에 대해 테일러 전개를 적용한다.
1 − 4 x = ( 1 − 4 x ) 1 2 = ∑ n = 0 ∞ ( 1 2 n ) ( − 4 x ) n = 1 − 2 x + ∑ n = 2 ∞ 1 n ! ∏ r = 0 n − 2 1 2 ( − 1 2 − r ) ( − 4 ) n x n = 1 − 2 x + ∑ n = 2 ∞ 1 n ! ( − 1 ) n − 1 ( 2 n − 3 ) ! ! 2 n ( − 1 ) n 4 n x n = 1 − 2 x − ∑ n = 2 ∞ ( 2 n − 3 ) ! ! n ! 2 n x n = 1 − 2 x − ∑ n = 2 ∞ ( 2 n − 3 ) ! n ! ( n − 2 ) ! 2 n − 2 2 n x n = 1 − 2 x − ∑ n = 2 ∞ 4 ( 2 n − 3 ) ! n ! ( n − 2 ) ! x n = 1 − 2 x − ∑ n = 2 ∞ 4 ⋅ 2 n ( 2 n − 1 ) ( 2 n − 2 ) ( 2 n − 3 ) ! 2 2 n ( n − 1 ) ( 2 n − 1 ) n ! ( n − 2 ) ! x n = 1 − 2 x − ∑ n = 2 ∞ ( 2 n ) ! ( 2 n − 1 ) ( n ! ) 2 x n = − ∑ n = 0 ∞ 1 2 n − 1 ( 2 n n ) x n \displaystyle \begin{aligned} \sqrt{1-4x} &= \left( 1-4x \right)^{\frac 12} = \sum_{n=0}^\infty \binom{\frac 12}n \left( -4x \right)^n = 1 -2x + \sum_{n=2}^\infty \frac 1{n!} \prod_{r=0}^{n-2} \frac 12 \left( - \frac 12 - r \right) \left( -4 \right)^n x^n \\ &= 1 - 2x + \sum_{n=2}^\infty \frac 1{n!} \frac{ \left( -1 \right)^{n-1} (2n-3)!!}{2^n} \left( -1 \right)^n 4^n x^n = 1 - 2x - \sum_{n=2}^\infty \frac{(2n-3)!!}{n!} 2^n x^n \\ &= 1 - 2x - \sum_{n=2}^\infty \frac{(2n-3)!}{n! \left( n-2 \right)! 2^{n-2}} 2^n x^n = 1 - 2x - \sum_{n=2}^\infty \frac{4 \left( 2n-3 \right)!}{n! \left( n-2 \right)!} x^n \\ &= 1 - 2x - \sum_{n=2}^\infty \frac{ 4 \cdot 2n \left( 2n-1 \right) \left( 2n-2 \right) \left( 2n-3 \right)!}{2^2 n\left( n-1 \right) \left( 2n-1 \right) n! \left( n-2 \right)!} x^n = 1 - 2x - \sum_{n=2}^\infty \frac{(2n)!}{\left( 2n-1 \right) \left( n! \right)^2}x^n \\ &= -\sum_{n=0}^\infty \frac 1{2n-1} \binom{2n}n x^n \end{aligned} 1 − 4 x = ( 1 − 4 x ) 2 1 = n = 0 ∑ ∞ ( n 2 1 ) ( − 4 x ) n = 1 − 2 x + n = 2 ∑ ∞ n ! 1 r = 0 ∏ n − 2 2 1 ( − 2 1 − r ) ( − 4 ) n x n = 1 − 2 x + n = 2 ∑ ∞ n ! 1 2 n ( − 1 ) n − 1 ( 2 n − 3 )!! ( − 1 ) n 4 n x n = 1 − 2 x − n = 2 ∑ ∞ n ! ( 2 n − 3 )!! 2 n x n = 1 − 2 x − n = 2 ∑ ∞ n ! ( n − 2 ) ! 2 n − 2 ( 2 n − 3 )! 2 n x n = 1 − 2 x − n = 2 ∑ ∞ n ! ( n − 2 ) ! 4 ( 2 n − 3 ) ! x n = 1 − 2 x − n = 2 ∑ ∞ 2 2 n ( n − 1 ) ( 2 n − 1 ) n ! ( n − 2 ) ! 4 ⋅ 2 n ( 2 n − 1 ) ( 2 n − 2 ) ( 2 n − 3 ) ! x n = 1 − 2 x − n = 2 ∑ ∞ ( 2 n − 1 ) ( n ! ) 2 ( 2 n )! x n = − n = 0 ∑ ∞ 2 n − 1 1 ( n 2 n ) x n
!!는 이중 계승 기호로
2 2 2 씩 빼서 곱하라는 뜻이다. 위 식을 대입해서 정리하면
c ( x ) = ∑ n = 0 ∞ C n x n = 1 − 1 − 4 x 2 x = 1 2 x ( 1 + ∑ n = 0 ∞ 1 2 n − 1 ( 2 n n ) x n ) = 1 2 x ∑ n = 1 ∞ 1 2 n − 1 ( 2 n n ) x n = ∑ n = 1 ∞ 1 2 ( 2 n − 1 ) ( 2 n n ) x n − 1 = ∑ n = 0 ∞ 1 2 ( 2 n + 1 ) ( 2 n + 2 n + 1 ) x n = ∑ n = 0 ∞ ( 2 n + 2 ) ! 2 ( 2 n + 1 ) { ( n + 1 ) ! } 2 x n = ∑ n = 0 ∞ ( 2 n ) ! ( n + 1 ) ! n ! x n = ∑ n = 0 ∞ ( 2 n ) ! ( n + 1 ) ( n ! ) 2 x n = ∑ n = 0 ∞ 1 n + 1 ( 2 n n ) x n ∴ C n = 1 n + 1 ( 2 n n ) \displaystyle \begin{aligned} c \left( x \right) &= \sum_{n=0}^\infty C_n x^n = \frac{1 - \sqrt{1-4x}}{2x} = \frac 1{2x} \left( 1 + \sum_{n=0}^\infty \frac 1{2n-1} \binom{2n}n x^n \right) = \frac 1{2x} \sum_{n=1}^\infty \frac 1{2n-1} \binom{2n}n x^n \\ &= \sum_{n=1}^\infty \frac 1{2\left( 2n-1 \right)} \binom{2n}n x^{n-1} = \sum_{n=0}^\infty \frac 1{2\left( 2n+1 \right)} \binom{2n+2}{n+1} x^n = \sum_{n=0}^\infty \frac{(2n+2)!}{2\left( 2n+1 \right) \left\{(n+1)! \right\}^2}x^n \\ &= \sum_{n=0}^\infty \frac{(2n)!}{(n+1)!n!}x^n = \sum_{n=0}^\infty \frac{(2n)!}{\left( n+1 \right) \left( n! \right)^2} x^n \\ &= \sum_{n=0}^\infty \frac 1{n+1} \binom{2n}n x^n \end{aligned} \\ \therefore C_n = \frac 1{n+1} \binom{2n}n c ( x ) = n = 0 ∑ ∞ C n x n = 2 x 1 − 1 − 4 x = 2 x 1 ( 1 + n = 0 ∑ ∞ 2 n − 1 1 ( n 2 n ) x n ) = 2 x 1 n = 1 ∑ ∞ 2 n − 1 1 ( n 2 n ) x n = n = 1 ∑ ∞ 2 ( 2 n − 1 ) 1 ( n 2 n ) x n − 1 = n = 0 ∑ ∞ 2 ( 2 n + 1 ) 1 ( n + 1 2 n + 2 ) x n = n = 0 ∑ ∞ 2 ( 2 n + 1 ) { ( n + 1 )! } 2 ( 2 n + 2 )! x n = n = 0 ∑ ∞ ( n + 1 )! n ! ( 2 n )! x n = n = 0 ∑ ∞ ( n + 1 ) ( n ! ) 2 ( 2 n )! x n = n = 0 ∑ ∞ n + 1 1 ( n 2 n ) x n ∴ C n = n + 1 1 ( n 2 n )
카탈랑 수는 다음을 포함한 수많은 조합문제들의 답으로 등장한다. Richard Stanley의 조합론 교과서 'Enumerative Combinatorics'
에선 이런 예시들 66가지(...)가 연습문제로 나온다고 한다.
정
n n n 다각형에 대각선을 그어 삼각형으로 분할하는 방법의 수
딕 경로(Dyck paths): (0,0)에서 (n,n)까지 격자점을 따라 오른쪽(즉 (1,0)만큼) 혹은 위로(즉 (0,1)만큼) 한 칸씩 이동하는 경로 중, 대각선
x = y x=y x = y 좌상단으로 넘어가지 않는 경로의 개수
각각
n n n 개의 왼쪽 괄호와 오른쪽 괄호를 나열하는데 괄호가 서로 맞아떨어지는 문자열의 개수. 예로
n = 2 n=2 n = 2 이면 (()), ()()의 두 가지 경우가 있다
크기
2 × n 2 \times n 2 × n 짜리 표의 각 칸에 1부터
2 n 2n 2 n 까지의 숫자를 집어넣는데, 아래로 가거나 오른쪽으로 갈수록 수가 커지는 방법의 수
이들의 대부분 경우에선 서로간의 조합론적 일대일대응을 찾을 수 있고, 일대일대응을 관찰하기 힘들더라도 상단의 점화식
C n + 1 = ∑ i = 0 n C i C n − i C_{n+1}=\sum_{i=0}^n C_i C_{n-i} C n + 1 = ∑ i = 0 n C i C n − i 을 유도할 수 있는 경우가 많다. 한편 위의 딕 경로 문제에 대해선 점화식과 독립적으로
C n = ( 2 n n ) − ( 2 n n − 1 ) \displaystyle C_n = \binom{2n}{n} - \binom{2n}{n-1} C n = ( n 2 n ) − ( n − 1 2 n )
을 얻어내어 다음처럼 풀이하는 것도 가능하다. 만약 대각선을 넘어가는 경로가 있다면, 직선
l : y = x + 1 l:y=x+1 l : y = x + 1 과 만나야 한다.
A = ( 0 , 0 ) A=(0,0) A = ( 0 , 0 ) 에서
B = ( n , n ) B=(n,n) B = ( n , n ) 으로 가는 경로가
l l l 과 만나는 최초의 점을
P P P 라 하면,
P → B P \rightarrow B P → B 의 경로 부분만
l l l 에 대칭시켜 변경해
A → P → ( n − 1 , n + 1 ) A \rightarrow P \rightarrow (n-1,n+1) A → P → ( n − 1 , n + 1 ) 의 경로를 얻을 수 있다. 따라서 대각선을 넘어가는 경로는
( 0 , 0 ) (0,0) ( 0 , 0 ) 에서
( n − 1 , n + 1 ) (n-1,n+1) ( n − 1 , n + 1 ) 까지 이동하는 경로와 일대일대응되므로 그 개수는
( 2 n n − 1 ) \binom{2n}{n-1} ( n − 1 2 n ) 개가 된다.
